package 递归回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No46全排列 {

    /**
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     *
     * 示例:
     *
     * 输入: [1,2,3]
     * 输出:
     * [
     *   [1,2,3],
     *   [1,3,2],
     *   [2,1,3],
     *   [2,3,1],
     *   [3,1,2],
     *   [3,2,1]
     * ]
     */

    List<List<Integer>> lists;

    public List<List<Integer>> permute(int[] nums) {
        lists=new ArrayList<>(nums.length);
        dg(new ArrayDeque<>(),nums);
        return lists;
    }

    private void dg(Deque<Integer> stack,int[] nums){

        if(stack.size()==nums.length){
            lists.add(new ArrayList<>(stack));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if(stack.contains(nums[i]))//如果用boolean[nums.length()]数组判断就可以更快
                continue;
            stack.addLast(nums[i]);
            dg(stack,nums);
            stack.removeLast();
        }
    }

}
